The recent rise in popularity of online activity, e.g., purchasing of products, has created large quantities of data about associations between entities. The data is often organized and kept in records for ease of access by multiple users or applications. When the data is organized in electronically accessible records, it is managed and updated by computers. These electronically accessible records can be stored into operational databases. Users and applications can then query these operational databases to access the data. However, the data contain many private details about individuals and associations between various entities. For example, the data may contain association between customers and products (e.g., medications, or drugs) bought from a particular store, e.g., a pharmacy. Although such data can be very useful for scientific research, privacy concerns will require that the data be anonymized before it is made available to users. For example, the data may be represented in the form of a large, sparse bipartite graph. One anonymization approach is to add or to delete some edges in the graph structure. However, adding or deleting edges may radically alter the graph structure, thereby limiting the usability of the data for an analysis involving the graph structure.